package com.aug_leo.datastructure.queue;

import java.util.Iterator;

/**
 * 仅用 head, tail 判断空满, head, tail 需要换算成索引值
 * head 和 tail 不断递增，用到索引时，再用它们进行计算，两个问题
 * <ul>
 *     <li>如何保证 head 和 tail 自增超过正整数最大值的正确性</li>
 *     <li>如何让取模运算性能更高</li>
 * </ul>
 * 答案: 让 capacity 为 2 的幂
 *
 * @param <E> 队列中元素类型
 */
public class ArrayQueue3<E> implements Queue<E>, Iterable<E> {

    /*
        求模运算:
        - 如果除数是 2 的 n 次方
        - 那么被除数的后 n 位数即为余数（模）
        - 求被除数的后 n 位方法: 与2^n-1 按位与
     */

    private final E[] array; // 循环数组
    int head = 0; // 头指针
    int tail = 0; // 尾指针


    @SuppressWarnings("all")
    public ArrayQueue3(int capacity) {
        // 1.抛异常
        /*if ((capacity & capacity - 1) != 0) {
            throw new IllegalArgumentException("capacity 必须是2的幂");
        }*/

        // 2.改成 2^n     13 -> 16    22 -> 32
        capacity -= 1;
        capacity |= capacity >> 1;
        capacity |= capacity >> 2;
        capacity |= capacity >> 4;
        capacity |= capacity >> 8;
        capacity |= capacity >> 16;
        capacity++;
        array = (E[]) new Object[capacity];

    }

    /*
        head = 0
        tail = 3 % 3
        capacity = 3


        0   1   2
        a   b   c
     */

    /**
     * 向队列尾插入值. 有的习惯命名为 enqueue
     *
     * @param value 待插入值
     * @return 插入成功返回 true, 插入失败返回 false
     */
    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
//        array[(int) Integer.toUnsignedLong(tail) % array.length] = value;
        array[tail & array.length - 1] = value;
        tail++;
        return true;
    }

    /**
     * 从对列头获取值, 并移除. 有的习惯命名为 dequeue
     *
     * @return 如果队列非空返回对头值, 否则返回 null
     */
    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        E value = array[head & array.length - 1];
        head++;
        return value;
    }

    /**
     * 从对列头获取值, 不移除
     *
     * @return 如果队列非空返回对头值, 否则返回 null
     */
    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return array[head & array.length - 1];
    }

    /**
     * 检查队列是否为空
     *
     * @return 空返回 true, 否则返回 false
     */
    @Override
    public boolean isEmpty() {
        return head == tail;
    }

    /**
     * 检查队列是否已满
     *
     * @return 满返回 true, 否则返回 false
     */
    @Override
    public boolean isFull() {
        return tail - head == array.length;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int pointer = head;

            @Override
            public boolean hasNext() {
                return pointer != tail;
            }

            @Override
            public E next() {
                E value = array[pointer & array.length - 1];
                pointer++;
                return value;
            }
        };
    }

    public static void main(String[] args) {
/*        // 验证 tail - head 不会有问题
        System.out.println(Integer.MAX_VALUE);
        // tail 已经自增为负数
        int head = 1_900_000_000;
        int tail = 2_100_000_000;
        for (int i = 0; i < 20; i++) {
            tail += 100_000_000;
            System.out.println(Integer.toUnsignedLong(tail) + " " + Integer.toUnsignedLong(head) + " " + (tail - head));
        }
        // 最后一次显示负数是因为 tail-head 4100000000-1900000000=2200000000 也超过了正整数最大值,而实际这种情况不可能发生(数组最大长度为正整数最大值)

        // tail 和 tail 都成了负数
        System.out.println("===========================");
        head = -2094967296; // 2200000000
        tail = -2094967296; // 2200000000
        for (int i = 0; i < 20; i++) {
            tail += 100_000_000;
            System.out.println(Integer.toUnsignedLong(tail) + " " + Integer.toUnsignedLong(head) + " " + (tail - head));
        }*/

        // 求离c最近，比c大的 2^n (方法1)
        int c = 32;

        /*
            2^4     = 16
            2^4.?   = 30
            2^5     = 32

              (int)log2(30) + 1
            2

            log2(x) = log10(x) / log10(2)

            1
            10      2^1
            100     2^2
            1000    2^3
         */

        /*int n = (int) (Math.log10(c-1) / Math.log10(2)) + 1;
        System.out.println(n);
        System.out.println(1 << n);*/

        // 求离c最近，比c大的 2^n (方法2)
        c--;
        c |= c >> 1;
        c |= c >> 2;
        c |= c >> 4;
        c |= c >> 8;
        c |= c >> 16;
        c++;
        System.out.println(c);
    }
}
